package com.lee.algorithm.array;

import static com.lee.algorithm.sort.SortUtil.print;
import static com.lee.algorithm.sort.SortUtil.swap;

/***
 * @description 堆
 * @author 青石路
 * @date 2022/3/15 11:05
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,3,2,8};
        /*for (int i=arr.length/2-1; i>=0; i--) {
            bigHeap(arr, i, arr.length);
            // smallHeap(arr, i, arr.length);
        }*/
        // bigHeapSort(arr);
        smallHeapSort(arr);
        print(arr);
    }

    /**
     * 大顶堆化
     *      大顶堆：每个结点的值都大于或等于其左右孩子结点的值，并未要求左右孩子的大小关系
     *      arr 初始状态可看作是一个普通的堆
     *      叶子节点索引：arr.length/2 ~ arr.length-1 是叶子节点
     *      非叶子节点索引：0 ~ arr.length/2-1
     *
     *      迭代处理以 arr[index] 为起点的树
     *
     * @param arr
     * @param index 当前树的起点索引
     * @param heapSize 堆大小，0 ~ heapSize-1 范围进行堆化
     */
    public static void bigHeap(int[] arr, int index, int heapSize) {

        // 左节点索引， 那么右节点索引：left + 1
        int left = index * 2 + 1;

        /**
         * index位置的数能否一直往下移动
         */
        while (left < heapSize) {

            // 取左、右元素中大的索引
            int largest = (left + 1 < heapSize) && (arr[left+1] > arr[left]) ? left+1 : left;

            // 取父和较大的孩子之间 大值的索引
            largest = arr[largest] > arr[index] ? largest : index;

            if (largest == index) {
                // 以 index 节点为根节点的树已经是大顶堆，无需再调整，直接跳出循环
                break;
            }

            // 交换
            swap(arr, largest, index);

            // index 来到大孩子节点的位置，作为新的起点
            // 大的替换上去后，下来的节点不一定比它的左右节点大，需要重新调整下来的节点和它的左右节点
            index = largest;
            left = index * 2 + 1;
        }
    }

    /**
     * 堆化
     *      迭代处理以 arr[index] 为起点的树
     * @param arr
     * @param index 当前树的起点索引
     * @param heapSize 堆大小，0 ~ heapSize-1 范围进行堆化
     * @author 博客园 @ 青石路
     */
    public static void shiftDown(int[] arr, int index, int heapSize) {

        // 左节点索引， 那么右节点索引：left + 1
        int left = index * 2 + 1;

        /**
         * shiftDown 过程
         */
        while (left < heapSize) {

            // 取左、右元素中小的索引
            int smallest = (left + 1 < heapSize)
                    && (arr[left] > arr[left+1]) ? left+1 : left;

            // 取父和较小的孩子之间 小值的索引
            smallest = arr[smallest] > arr[index] ? index : smallest;

            if (smallest == index) {
                // 以 index 节点为起点的树已经是小顶堆，无需再调整，直接跳出循环
                break;
            }

            // 交换
            swap(arr, smallest, index);

            // index 来到小孩子节点的位置，作为新的起点
            // 小的替换上去后，下来的节点不一定比它的左右节点小，需要重新调整下来的节点和它的左右节点
            index = smallest;
            left = index * 2 + 1;
        }
    }

    /**
     * 堆排序，升序排序
     * @param arr
     */
    public static void bigHeapSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        int heapSize = arr.length;

        // 构建初始大顶堆
        for (int i=arr.length/2-1; i>=0; i--) {
            bigHeap(arr, i, arr.length);
        }

        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            bigHeap(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 堆排序，降序排序
     * @param arr
     */
    public static void smallHeapSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        int heapSize = arr.length;

        // 构建初始小顶堆
        for (int i=arr.length/2-1; i>=0; i--) {
            shiftDown(arr, i, arr.length);
        }

        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            shiftDown(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
}
